package fanruan;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @author blh
 * @date 2024年06月28日 10:58
 */

public class test2 {

    ArrayList<Integer> res = new ArrayList<>();

    public ArrayList<Integer> MinimumK(int N) {
        // 感觉是回溯算法
        backTrace(N, new ArrayList<>(), 0);
        Collections.sort(res, (o1, o2) -> Integer.compare(o2, o1));
        return res;

    }

    private void backTrace(int target, ArrayList<Integer> curList, int curSum) {
        if ((target - curSum) < 8) {
            for (int i = 0; i < target - curSum; i++) {
                curList.add(1);
            }
            if (res.isEmpty()) {
                res = new ArrayList<>(curList);
            } else {
                if (res.size() > curList.size()) {
                    res = new ArrayList<>(curList);
                }
            }
            return;
        }
        int gap = target - curSum;
        int tri = get3(gap);
        for (int i = 2; i <= tri; i++) {
            curList.add(i);
            backTrace(target, curList, curSum + i * i * i);
            curList.remove(curList.size() - 1);
        }

    }

    private int get3(int gap) {
        int tri = 1;
        for (int i = 1; i < gap; i++) {
            if (i * i * i <= gap) {
                tri = i;
            } else {
                break;
            }
        }
        return tri;
    }

}
